Sort in C++ STL
Sort in C++ STL
The thief problem
Fractional knapsack problem
Chocolate Distribution Problem
Sort elements of array by frequency
In this video we'll talk about the problem we are given an array of items we need to sort these items according to their frequency
you are given arrival and departure times of the guests, you need to find the time to go to the pary so that you can meet maximum people.
make_heap() in C++ STL
merge() in C++ STL
next_permutation() in C++ STL
rotate() in C++ STL
prev_permutation() in C++ STL
Syntax 1: sort(arr, arr + n);
This syntax takes the address of first element in the array
and address just after the last element and sorts the
array in increasing order.
Syntax 2: sort(c.begin(), c.end());
This syntax takes the address of first element of the container
and address just after the last element and sorts the
container in increasing order.
How to sort in descending order?
The sort() function takes a third parameter that is used to specify the order in which elements are to be sorted. We can pass “greater()” function to sort in descending order. This function does a comparison in a way that puts greater elements before.Array after sorting using default sort is :
1 5 6 7 8 9
Array after sorting in decreasing order:
9 8 7 6 5 1
Vector after sorting using default sort is :
5 7 10 20
Vector after sorting in decreasing order:
20 10 7 5
How to sort in particular order?
We can also write our own comparator function and pass it as a third parameter. This “comparator” function returns a value; convertible to bool, which basically tells us whether the passed “first” argument should be placed before the passed “second” argument or not.2 8
3 10
5 4
Time Complexity and Internal Working
Worst case and Average Case Time Complexity: The worst and average case time complexity of sort() function in O(N*logN), where N is the number of elements in the container.Input: N = 10, K = 50
cost = { 1, 12, 5, 111, 200, 1000, 10, 9, 12, 15 }
Output: 6
Explanation: Toys with amount 1, 5, 9, 10, 12, and 12
can be purchased resulting in a total amount of 49. Hence,
the maximum number of toys is 6.
Input: N = 7, K = 50
cost = { 1, 12, 5, 111, 200, 1000, 10 }
Output: 4

6
Input : arr[] = {7, 3, 2, 4, 9, 12, 56}
m = 3
Output: Minimum Difference is 2
Explanation: We have seven packets of chocolates and
we need to pick three packets for 3 students
If we pick 2, 3 and 4, we get the minimum
difference between the maximum and minimum packet
sizes.

// C++ program to solve chocolate distribution
// problem
#include <bits/stdc++.h>
using namespace std;
// arr[0..n-1] represents sizes of packets
// m is number of students.
// Returns minimum difference between maximum
// and minimum values of distribution.
int findMinDiff(int arr[], int n, int m)
{
// if there are no chocolates or number
// of students is 0
if (m == 0 || n == 0)
return 0;
// Sort the given packets
sort(arr, arr + n);
// Number of students cannot be more than
// number of packets
if (n < m)
return -1;
// Largest number of chocolates
int min_diff = INT_MAX;
// Find the subarray of size m such that
// difference between last (maximum in case
// of sorted) and first (minimum in case of
// sorted) elements of subarray is minimum.
int first = 0, last = 0;
for (int i = 0; i + m - 1 < n; i++) {
int diff = arr[i + m - 1] - arr[i];
if (diff < min_diff) {
min_diff = diff;
first = i;
last = i + m - 1;
}
}
return (arr[last] - arr[first]);
}
int main()
{
int arr[] = { 12, 4, 7, 9, 2, 23, 25, 41,
30, 40, 28, 42, 30, 44, 48,
43, 50 };
int m = 7; // Number of students
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Minimum difference is "
<< findMinDiff(arr, n, m);
return 0;
}
Minimum difference is 10
Input: N = 10, K = 50, cost = { 1, 12, 5, 111, 200, 1000, 10, 9, 12, 15 }
Output: 6
Explanation: Toys with amount 1, 5, 9, 10, 12, and 12 can be
purchased resulting in a total amount of 49. Hence, maximum number of toys is 6.

6
Input: arr[] = {2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12}
Output: 3 3 3 3 2 2 2 12 12 4 5
Explanation:
No.: Freq
2 : 3
3 : 4
4 : 1
5 : 1
12 : 2
// C++ program to sort elements by frequency
#include <bits/stdc++.h>
using namespace std;
// Function to compare two pairs
bool compare(pair<int,int> &p1,
pair<int, int> &p2)
{
// If frequencies are same, compare the values
if (p1.second == p2.second)
return p1.first < p2.first;
return p1.second > p2.second;
}
// Function to print elements
void printSorted(int arr[], int n)
{
// Store items and their frequencies
map<int, int> m;
for (int i = 0; i < n; i++)
m[arr[i]]++;
// No. of distinct values are equal to the size of the map
int s = m.size();
// An array of pairs
pair<int, int> p[s];
// Fill (val, freq) pairs in an array of pairs
int i = 0;
for (auto it = m.begin(); it != m.end(); ++it)
p[i++] = make_pair(it->first, it->second);
// Sort the array of pairs
sort(p, p + s, compare);
cout << "Elements sorted by frequency are: ";
for (int i = 0; i < s; i++)
{
int freq = p[i].second;
while (freq--)
cout << p[i].first << " ";
}
}
int main()
{
int arr[] = {2, 3, 2, 4, 5, 12, 2, 3,
3, 3, 12};
int n = sizeof(arr)/ sizeof(arr[0]);
printSorted(arr, n);
return 0;
}
Elements sorted by frequency are: 3 3 3 3 2 2 2 12 12 4 5
1, 2, 3, 5, 4Therefore for a sequence of size N, there will be N! permutations.
1, 2, 4, 3, 5
1, 2, 4, 5, 3
1, 2, 5, 3, 4
1, 2, 5, 4, 3
1, 3, 2, 4, 5
...
...
...
bool next_permutation (BidirectionalIterator first,
BidirectionalIterator last);
Input: {1, 2, 3, 4, 5}
Output: {1, 2, 3, 5, 4}
Input: {1, 2, 5, 4, 3}
Output: {1, 3, 2, 4, 5}
Input: {5, 4, 3, 2, 1}
Output: {5, 4, 3, 2, 1}
1 3 2 4 5
Algorithm for next_permutation() function:
Let the initial sequence be:{1, 2, 5, 4, 3}
For the given sequence {1, 2, 5, 4, 3},
x would be 2
For the given sequence {1, 2, 5, 4, 3}
y = 3
After swap: {1, 3, 5, 4, 2}
After reversing: {1, 3, 2, 4, 5}
left(i) = 2i + 1
Eg., left(1) = 2*1 + 1 = 1 (2)
right(i) = 2i + 2
Eg., right(1) = 2*1 + 2 = 4 (3)
parent(i) = floor((i - 1)/2)
parent(1) = floor((1 - 1) / 2) = 0 (10)
void make_heap(RandomAccessIterator first, RandomAccessIterator last)
void make_heap (RandomAccessIterator first, RandomAccessIterator last, comp)
30
How to convert a container to MIN_HEAP
The make_heap() function takes a third parameter as specified in Syntax 2 that is used to specify the order in which elements are to be arranged in the heap. We can pass “greater()” function to convert the heap into a MIN_HEAP. This function reverses the order of comparison.6
Implementation of push_heap() and pop_heap() function
push_heap(): The push_heap() function is used to insert elements into heap. The size of the heap is increased by 1 and the new element is placed appropriately in the heap. Thios is similar to the insert() function of heap.6
7
2
Vector = {15, 6, 7, 12, 30}Heap = {6, 7, 12, 15, 30}Print 6
Current Heap = {7, 12, 15, 30}Print 7
Current Heap: {2, 7, 12, 15, 30}Print 2
Implementation of sort_heap() function
The sort_heap() function is used to sort the heap in either an increasng or decreasing order, based on the 3rd parameter as mentioned in in Syntax 2. By default, the sort_heap() function sorts the heap in an increasing order.sort_heap(start_address, end_address, order())
30 15 12 7 6
Input: a[] = {3, 20, 40}
b[]: {2, 10, 12}
Output: a[] = {2, 3, 10}
b[]: {12, 20, 40}
Explanation: The first array contains the smaller 3 elements.
The second array contains the greater 3 elements.
Input: a[] = {30, 40}
b[]: {2, 8, 9, 10}
Output: a[] = {2, 8}
b[]: {9, 10, 30, 40}
Explanation: The first array contains the smaller 2 elements.
The second array contains the greater 4 elements.
Input: a[] = {3, 8}
b[]: {4, 5, 6}
Output: a[] = {3, 4}
b[]: {5, 6, 8}
Explanation: The first array contains the smaller 2 elements.
The second array contains the greater 3 elements.
// CPP program to illustrate
// sort_heap() function
#include <algorithm>
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
// merge() function for in-place sort and merge
void merge(int a[], int b[], int m, int n)
{
// Traversing the first array
for (int i = 0; i < m; i++) {
if (a[i] > b[0]) {
// Popping the element at root
pop_heap(b, b + n, greater<int>());
// Swapping the a[i] with popped element
swap(a[i], b[n - 1]);
// Pushing the popped element back
push_heap(b, b + n, greater<int>());
}
}
// Displaying the first array
for (int i = 0; i < m; i++)
cout << a[i] << " ";
cout << endl;
// Displaying the second array
for (int i = 0; i < n; i++)
cout << b[i] << " ";
}
// Drivers Method
int main()
{
int a[] = { 3, 20, 40 };
int m = 3;
int b[] = { 2, 10, 12 };
int n = 3;
// Calling the merge() function
merge(a, b, m, n);
return 0;
}2 3 10
12 20 40
1, 2, 3So for {2, 1, 3}, the previous permutation is {1, 3, 2}.
1, 3, 2
2, 1, 3
2, 3, 1
3, 1, 2
3, 2, 1
bool prev_permutation(BidirectionalIterator first,
BidirectionalIterator last);
Input: {2, 1, 3}
Output: {1, 3, 2}
Input: {2, 3, 1}
Output: {2, 1, 3}
Input: {1, 3, 2, 4, 5}
Output: {1, 2, 5, 4, 3}
Input: {5, 4, 1, 2, 3}
Output: {5, 3, 4, 2, 1}
5 3 4 2 1
Algorithm for prev_permutation() function:
Let the initial sequence be:{5, 4, 1, 2, 3}
For the given sequence {5, 4, 1, 2, 3},
x would be 4
For the given sequence {5, 4, 1, 2, 3}
y = 3
After swap: {5, 3, 1, 2, 4}
After reversing: {5, 3, 4, 2, 1}
bool reverse(BidirectionalIterator first,
BidirectionalIterator last);
Input: vector v = {10, 20, 30}
Operation: reverse(v.begin(), v.end());
Output: {30, 20, 10}
Explanation: In the above function, we have applied reverse()
in the range of [v.begin, v.end). Here v.end points to the element
beyond the last element of the vector.
30 20 10
Input: vector v = {10, 20, 30, 40, 50}
Operation: reverse(v.begin()+1, v.end());
Output: {10, 50, 40, 30, 20}
Explanation: In the above function, we have applied reverse()
in the range of [1, end), therefore the 0th element remains unaffected. Here v.end
points to the element beyond the last element of the vector.
10 50 40 30 20
Input: arr[] = {10, 20, 30, 40, 50}
Operation: reverse(arr, arr+5);
Output: {50, 40, 30, 20, 10}
Explanation: In the above function, we have applied reverse()
in the range of [0, 5), therefore the 0th element remains unaffected. Here arr+5
points to the element beyond the last element of the array.
50 40 30 20 10
Input: String s= "geeks"
Operation: reverse(s.begin(), s.end());
Output: skeeg
Explanation: In the above function, we have applied reverse()
function on the string. Here s.end() points to the element beyond
the last element of the string.
skeeg
merge(container1_first, container1_last,
container2_first, container2_last,
container3_first)
Input: v1 = {10, 20, 40}
v2 = {5, 15, 30}
Output: v3 = {5, 10, 15, 20, 30, 40}
5 10 15 20 30 40
Input: ar1= {10, 20, 30}
ar2 = {5, 15, 40, 80}
Output: ar3 = {5, 10, 15, 20, 30, 40, 80}
5 10 15 20 30 40 80